perm filename NOTES.EVA[LSP,JRA]5 blob
sn#249372 filedate 1976-11-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .SS(Alternatives to %3prog%1,,P253:)
C00014 00003 .SS(Extensions to %3eval%1,,P187:)
C00022 00004 .ss(Non-recursive control structures)
C00029 00005 .ss(%3eval%1 with explicit access,,P209:)
C00053 00006 .ss(%3eval%1 with explicit control)
C00069 00007 .SS(An evaluator for %3prog%1,,P211:)
C00100 00008 .CENT(Problems)
C00102 00009 .SS(Alternatives to %3eval%1)
C00118 00010 .CENT(Problems)
C00120 ENDMK
C⊗;
.SS(Alternatives to %3prog%1,,P253:)
The %3prog%1 feature of LISP is an effective means for encoding iterative
algorithms, however it suffers from a few draw-backs. For example,
The label-and-%3go%1 style of control is only a slight modification of
the control mechanisms which are typically used to control a hardware machine,
and thus the level of description which is required
tends to obscure the actual flow of the algorithm unless
the programmer is careful.
A slight extension to conditional expressions and
conditional statements can alleviate some of the confusion which is
likely when constucting complex %3prog%1s.
.P194:
As
conditionals are now defined, e%4i%* must be a single expression to be evaluated.
With the introduction of side effects,
it is convenient to extend conditionals to include components of the
form: p%4i%*#→#e%4i1%*; ... e%4in%*.
This extended component is to be evaluated as follows: if p%4i%* is true, then
evaluate the e%4ij%*'s from left to right, with the value of the component to be
the value of e%4in%*⊗↓This
extended conditional expression is available
on versions of LISP 1.6 on the PDP-10 ⊗↑[Moo#76]↑, ⊗↑[Qua#xx]↑, ⊗↑[Int#75]↑.←.
For example, this feature, used in %3prog%*s would allow us to replace:
.BEGIN TABIT2(10,14);
\\ ....
\\[p%41%* → %3go[l]]
\m
\\ ...
\\return[%et%*];
\%3l\%1e%41%*;
\\e%42%*;
\\ ...
\\%3go[m];
.END
with:
.BEGIN CENTER;
... [p%41%* → e%41%*;e%42%*; ... ] ...; %3return[%et%*]].
.END
The improved readibility is largely do to the localizing or "packaging" of
the actions with their initiators; we need not scan an arbitrarily long piece
of text to discover what the computation will be when the predicate is true.
Several languages have included more
"packaged" versions of iterative control. The motivation was similar
to that which we used in justifying recursive control: we didn't care
%2how%1 recursion was implemented, all we wished to discuss was the
%2effect%1 or %2behavior%1 of recursion⊗↓Indeed we %2could%1 have replaced
recursive control with an appropriate combination of label-and-%3go%1's.←.
Clearly an iterative unit must allow the programmer
a reasonable degree of freedom and naturalness in expression. What should also
be recognized is that the structural unit should be amenable to analysis
to the same degree as that allowed in recursion. We must be able to state
precise properties of algorithms which use these constructs, and we should be able
to prove properties of such algorithms.
With the control of the loop structure in the
language rather than in the hands of the programmer, the
static text and the dynamic flow of the execution have a close
relationship. General use of label-and-%3go%1's and assignments
does not maintain such properties.
Our iterative control construct should therefore capture all of the essential
ingredients of an iteration, and its semantics should be restricted such that
its static text does indeed reflect its dynamic flow.
Our first example is based on the MacLISP %3do%1 ⊗↑[Moo#76]↑. With some inessential
changes, its syntax is:
.BEGIN TABIT2(27,30);GROUP;
\%3do\[%1<var%41%1> <init%41%1> <step%41%1>;
\\ %1<var%42%1> <init%42%1> <step%42%1>;
\\ ...
\\ %1<var%4n%1> <init%4n%1> <step%4n%1>;
\\[<pred> → <exit>]
\\ <body> ]
.END
The construct captures the ideas of intialization and updating of variables nicely.
Each <var%4i%1> is initialized to its <init%4i%1>-value simultaneously.
Each <step%4i%1> is a form which will be evaluated upon proper completion
of each loop of the %3do%1. The <pred> is evaluated, and on giving value %et%1
the loop will terminate, returning the value of <exit>.
If <pred> gives %ef%1 then <body> is executed. This component of the %3do%1
is a %3prog%1 body; when the last statement in <body> is executed, the
<step%4i%1> forms are evaluated and assigned to the <var%4i%1>'s, and
another cycle of the %3do%1 is begun.
Since the <body> of the %3do%1 is a %3prog%1 body, the %3return%1 statement
may appear. This is an undesirable feature since the dynamic flow will
then diverge from the static text. But consider the %3do%1 version of %3member%1:
.BEGIN TABIT3(12,27,30);SELECT 3;GROUP;
\member <= λ[a;l]\do\[x l rest[x];
\\\ [null[x] → %ef%*]
\\\ [eq[first[x];a] → return[%et%*]] ]
.END
This algorithm could be expressed without %3return%1 but the
resulting program is unnecessarily complex.
An alternative iterative construct was proposed in ⊗↑[Wis#75]↑.
.BEGIN center;SELECT 3;GROUP;
repeat[%1<st-list%41%1>;%3while %1<pred%41%1>; <st-list%42%1>; %3until %1<pred%42%1>; <st-list%43%1>]
.END
where <pred%4i%1> is a predicate, and <st-list%4i%1> is a list of
statements. The list may be empty, but may not contain %3return%1s or %3go%1s.
The semantics is as follows: <st-list%41%1> is executed; <pred%41%1> is
then evaluated and if false we exit the %3repeat%1 with %ef%1. If <pred%41%1>
is true, then we execute <st-list%42%1> and test <pred%42%1>; if <pred%42%1> is true
we exit with %et%1, otherwise we execute <st-list%43%1> and iterate the loop
beginning again at <st-list%41%1>.
For example we could write %3member%1 as:
.BEGIN TABIT3(10,20,37);GROUP;SELECT 3; turn off "←";
\member <= λ[[a;l]
\\repeat[while [not[null[l]]; until [equal[a;first[l]];l ← rest[l] ]
.END
The difficulty which we encountered with the MacLISP %3do%1 has been
alleviated, however the %3repeat%1 construct has several shortcomings
of its own. In particular, we have no means for designating
what variables are to be initialized and incremented within the loop.
Such variables must be declared and initialized external
to the %3repeat%1; also the stepping of the loop variables must be done
using the assignment statement. Similarly the power of expression on leaving
the %3repeat%1 is limited; we cannot explicitly declare what
values are to be returned. The value is that of the appropriate <pred%4i%1>.
add do%4jra%1
.CENT(Problems)
.P136:
.P133:
I. Some of the generality of %3prog%*s can be controlled
by the use of a new control structure for list operations. The
construct is called %3lit%*⊗↓for %3l%1ist %3it%1erator ⊗↑[Bar#66]↑←.
%3lit%1 takes three arguments: a binary function %3f%1,
a list %3l%1, and a value %3v%1.
If %3l%1 is empty, give %3v%1; otherwise apply %3f%1 to the first element of
%3l%1 and the effect of applying %3lit%1 to the remainder of %3l%1.
.GROUP
For example %3append%* could be expressed as:
.BEGIN CENTERIT; SELECT 3;
←append <= λ[[x;y]lit[function[concat];x;y]]
.END
Give a non-%3prog%1 definition for %3lit%1.
.APART
.GROUP
.P193:
II. Here is another useful extension to LISP:
Instead of requiring that the body of a λ-definition
be a single expression: %9x%1 in %3λ[[#...#]%9x%*]%1, allow bodies of the form:
%9x%41%3;#...;#%9x%4n%3%1, giving rise to λ-definitions like
%3λ[[#...#]%9x%41%3;#...;#%9x%4n%3]%1. The application of such
a definition means: bind the λ-variables as usual, then evaluate the %9x%4i%1's
from left to right returning
as value, %9x%4n%1.
Extend the evaluator of {yonss(P6)} to handle such constructs.
.APART
III. Give an S-expr representation for the %3repeat%1 expression and add
%3repeat%1 to %3eval%1 of {yonss(P6)}.
.SS(Extensions to %3eval%1,,P187:)
The introduction of the %3prog%1-feature completes our
syntactic description of the
language constructs of LISP. We would like to give a new version of %3eval%1
which describes the semantics of %3prog%1s in a manner which accurately reflects
the techniques used in implementations. We could simply simulate %3prog%1 behavior
using recursive techniques, but the iterative control expressed in %3prog%1s
is an important idea in its own right and is a simple instance of
non-recursive control. A mechanism which faithfully implements such control
structures leads easily to the idea of %2⊗→generalized control structures↔←%1.
The second interesting feature introduced with %3prog%1s was the assignment
statement. Again, we could mirror most of the behavior of assignments
by careful use of the techniques of recursion and symbol tables, but such
modelling would not adequately reflect the intent or indeed the techniques
used in implementing such constructs. We could describe such implementations
in a low-level machine language, but such practice would only introduce
unnecessary details. Rather, we will describe an evaluator in LISP using
the techniques we have been developing. In the process we will elucidate
much more than just %3prog%1s and assignments; we will lay bare much more
of the behavior which was implicit in the previous evaluators. Those
evaluators used recursion in the explication of recursion, frequently depended on
call-by-value in the explanation of call-by-value, and suppressed much of the
detail of binding and look up. The Weizenbaum environments added more detail, but
failed to describe an explicit mechanism for the handling of partial computations,
neither showing where partial results were maintained or how the evaluator was to
remember where it was in an expression when it had to evaluate a sub-expression.
All of this detail will come out in the new evaluator. Since the
structure of the new %3eval%1 is quite different from those seen before, and since
the level of detail is more intense, we will proceed in several steps.
First we discuss some generalizations of the label-and-%3go%1
control structures. These ideas have importance in their own right when we
discuss actual interactive implementations of LISP. Next we develop
an %3eval%1 in which the handling of access structures is explicit. The
innovations in this evaluator will form the basic blocks which we will use
to model parameter passing and assignments. This evaluator will still be
recursively described, and will not handle the %3prog%1 feature. In the final
step we replace the recursion with explicit control and with this
change we have the basis for adequate treatment of non-recursive control.
Finally we present an evaluator which handles all of the %3prog%1-related
constructs.
.ss(Non-recursive control structures)
On {yon(P83)} we discussed the %3go%1 construct. In that discussion we
noted that the scope of the %3go%1 was not restricted to the current %3prog%1;
we need only locate an appropriate label in a %2dynamically%1 surrounding
expression. Thus we could jump out of an expression, passing through many
intervening expressions, whereas strict recursive control requires that we
exit functions in a level-by-level fashion.
This ability to exit across many levels of computation
finds applications
at the system level in interactive LISP implementations
and is also a useful programming
feature. For example, if some extraordinary condition occurs within a
computation we might wish to abort that whole endeavor. As things currently
stand we would have to supply an additional value in the range of each
function which could occur in that computation. Each function
would have to test for that exception-value and when it is found, return that
value to the caller. This is an effective, but not elegant, solution
to the problem. Notice that this is the solution posed in our
use of %9B%1 in conjunction with strict functions.
Indeed, a more elegant solution has its origins in the early LISP debugging
tools. If a computation produced an error detectable as %9B%1, then it
typically was the responsibility of the LISP controller to print an error
message and terminate the computation. Such behavior was acceptable for
simple computations.
As computations became more complex it became clear that the occurrence of
one error need not signal the termination of %2all%1 computation.
Particularly since the expressions were available as data structures, the
opportunity for self-correcting programs existed in LISP. Thus LISP needed
a mechanism for more selective control of error messages.
The early LISP systems supplied a pair of functions named ⊗→%3errset%1↔←
and ⊗→%3err%1↔←.
The function %3errset%1 evaluates its first argument in the current context.
If no error occurs in that evaluation, the result is %3concat%1ed onto
(#) and returned. If an error does occur then the value of the %3errset%1
is %ef%1. Notice that in either case the %3errset%1 terminates. We can test
the success of our calculation by sampling the value of %3errset%1:#%ef%1
implies failure; otherwise the %3first%1 element of the result is the
true value.
The user can also force the occurrence of an "error" by calling %3err%1.
The unary function %3err%1 returns the value of its argument to the dynamically
enclosing %3errset%1 or, if there is no such %3errset%1, the value
is returned as the final value of the computation.
For example if %3err%1 is restricted to returning values in a set disjoint
from those returned by a non-"error" computation,
then the user can test the value of %3errset%1 to discover the
type of "error".
.P195:
The freedom allowed by the %3errset-err%1 combination soon became exploited
in ways not originally intended. The use of %3errset%1 and %3err%1 in
non-error-handling contexts often became quite confusing. The
MacLISP ⊗↑[Moo#76]↑ dialect includes a pair of constructs named ⊗→%3catch%1↔← and
⊗→%3throw%1↔← to be used in these situations.
%3catch%1 and %3throw%1 are both binary functions. Both first arguments
are expressions; both second arguments are interpreted
like %3prog%1 labels.
%3catch%1[<form>;<label>] evaluates its first argument in
the current context, and returns
that value, except that if during that evaluation, a %3throw[%1<form>;<label>]
with the
same <label> is evaluated, then the value of %3throw%1's <form> is returned
immediately.
For example⊗↓⊗↑[Moo#76]↑←:
.BEGIN SELECT 3;GROUP;TABIT3(20,25,33);
\catch[\mapfirst[\function[λ[[x][x<0 → throw[x;negative];%et%3 → f[x]]]];
\\\y];
\\negative]
.END
Assuming %3y%1 is a list of numbers,
this expression will return a list of %3f%1 applied to each element of %3y%1
if each element of %3y%1 is non-negative,
otherwise it will return the first negative element of %3y%1.
.ss(%3eval%1 with explicit access,,P209:)
There are two major portions of the evaluation schemes which
should be subjected to closer scrutiny before we attempt to discuss
implementations: the access and binding structures, and the description of
recursive control.
This section will look at access and binding.
The Weizenbaum environments give a nice graphical representation of the
access structures, but it would be instructive to express these ideas
in terms of LISP functions. This would give us an algorithm, suitable for
implementation, and would describe the mechanisms of LISP at a more detailed level
than that in the evaluators of {yonss(P6)}. The description we will
give will involve primitive notions just as the prior %3eval%1's do, however
the level of detail which they capture will be more readily transcribed
to implementation devices.
As we have previously mentioned, the Weizenbaum environments leave much of the
detail of access and binding implicit. It will be a goal of this section
to fill in these details.
Recall that a Weizenbaum environment was created at function-entry time.
As we evaluated the arguments to a function, we saved the results
in some fashion and, when all arguments were evaluated we formed
a new local block, linking it on to the front of the existing environment,
and the resulting structure became the new environment. Since we need space
to contain the evaluated parameters, and since those results are then moved
into a environment block, we might as well make the space which is to contain
those evaluated parameters as much like an environment block as possible.
Indeed, the space requirements for the evaluated parameters is known: the
block must be as long as the number of formal parameters expected.
This requirement can be ascertained by examining the definition of the
function being called. Once the block is allocated, the actual parameters
are evaluated and the results are sent to the proper slot in the
allocated block. Such a block will be called a %2destination block%1; and the
operation of placing a result in a destination will be called %2sending%1.
Once all the evaluated parameters have been sent, we %2link%1 the completed
block into the front of the current environment.
The ideas expressed in this section are an embellishment of those of {yon(P212)}.
The main innovation is to allocate space for the evaluated arguments before
beginning their actual evaluation. The evaluator sends the values to
the allocated block
.BEGIN INDENT 0,11;GROUP;
Here are the primitive routines:
%21.%1 %3alloc_dest%1: This unary function is supplied with the formal parameter
list of a function, and supplies a new destination block with the formal
parameters placed in the name-section of the block. An internal pointer is
initialized to the first slot in the block. Thus:
.END
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
∞1 a destination block∞*
⊂ααααααα⊃
~ #αβα⊃
εαααπαααλ ↓ ∞1internal pointer∞*
~ ~ ~←$
εαααβαααλ
~ ~ ~
# # #
εαααβαααλ
~ ~ ~
%ααα∀ααα$
↑ ↑
∞1formal parameters values∞*
.END
.APART
.BEGIN INDENT 0,7;GROUP;
%22.%1 %3send%1: This is a binary function whose first argument is a destination
block
and whose second argument is a value to be sent. The value of %3send%1 is the
destination block. The effect of %3send%1 is to send its second argument to the
current destination slot. The internal pointer is %2not%1 updated; that is the
business of %3next%1.
.END
.BEGIN INDENT 0,7;GROUP;
%23.%1 %3next%1: This function takes a destination block as argument and moves
the internal pointer of the block to point to the
succeeding slot. The value of %3next%1 is the destination block. Thus
%3next%1 is an identity function with a side-effect.
.END
.BEGIN INDENT 0,7;GROUP;
%24.%1 %3link%1: %3link%1 takes a destination block and an environment as arguments
and links the destination block onto the front of the environment. The
resulting environment is the value of %3link%1. Since the internal pointer
is only used during the filling of the dest-block, we can assume that
%3link%1 replaces that pointer with a pointer to the previous environment.
.END
.BEGIN INDENT 0,8;GROUP;
%25.%1 %3receive%1: Sometimes we will wish to examine the result of a computation
before making a decision on how to proceed.
In particular, in conditional expressions we must
evaluate the predicate position before knowing how to handle the rest of the
conditional. The unary primitive %3receive%1 lets us look at the result of a
computation. The argument to %3receive%1 is a destination block, and the value
returned is the value in the current slot.
.END
In the following evaluators we will freely use the extended
conditional expressions and λ-expressions introduced on {yon(P194)} and {yon(P193)}.
The first evaluator is named %3deval%1, with the "%3d%1 coming from "destination".
.BEGIN TABIT2(15,25);SELECT 3;GROUP;
deval <= λ[[exp;env;dest]
\[isconst[exp] → send[dest;denote[exp]];
\ isvar[exp] → send[dest;lookup[exp;env]];
\ %et%3 → deval%41%3[func[exp]; arglist[exp]; env; dest] ]]
.END
.BEGIN NOFILL;TABS 15,27,37,46,51,58;TURN ON "\";SELECT 3;GROUP;
deval%41%3 <= λ[[fun;args;env;dest]
\[atom[fun] → \[iscond[fun] → devcond[args;env;dest]
\\ isprim[fun] → execute[\fun;
\\\\link[\evalargs[\args;
\\\\\\env;
\\\\\\alloc_dest[createvars[args]];
\\\\\env];
\\\\dest];
\\ %et%3 → deval[fun;env;dest]; deval%41%3[receive[dest];args;env;dest] ]
\ islambda[fun] → evalargs[\bodylist[fun];
\\\link[evalargs[args;env;alloc_dest[vars[fun]]]];env];
\\\dest]
\ %et%3 → deval[fun;env;dest]; deval%41%3[receive[dest];args;env;dest] ]]
.END
.BEGIN TABIT2(15,24);SELECT 3;GROUP;
evalargs <= λ[[args;env;dest]
\[null[args] →dest;
\ null[rest[args]] → deval[first[args];env;dest];
\ %et%3 → deval[\first[args];env;dest];
\\next[dest];
\\evalargs[rest[args];env;dest] ]]
execute <= λ[[fun;env;dest]send[dest;apply[fun;vals[env];( )]]]
.BEGIN FILL;SELECT 1;
Note that %3execute%1 resorts to %3apply%1 to handle primitive application.
.END
.APART
.GROUP
devcond <= λ[[args;env;dest]
\deval[pred[first[args]];env;dest];
\[receive[dest] → evalargs[condbody[first[args]];env;dest];
\ %et%3 → devcond[rest[args]; env;dest] ]]
.END
This new evaluator must be supplied with an initial destination as well as
being supplied with an initial symbol table. Also since the result of any
calculation is a destination block rather than just a simple value, we should
supply a selector to extract the desired value. For example, if we designate
%3val%1 as such a selector, and designate the atom %3TLB%1 as the repository
for the top level binding then:
.BEGIN CENTER;SELECT 3;
eval <= λ[[exp;env] val[deval[exp;env;alloc_dest[(TLB)]]]]
.END
More of the details of argument handling should now be understandable:
when a function
application has been recognized, the evaluator sets up a block to hold
the results of evaluating the actual parameters. If the function is a
primitive function then the name slots are filled with some system-created
names, otherwise the λ-variables are used.
.BEGIN GROUP;
.CENT(Problem)
.CENTER
Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.END
Notice that for most of the evaluation process, %3dest%1 is a passive element.
A new destination block is created on function applications, but that %3dest%1
is passed around as an argument through most of the pieces of the evaluator
without explicit modification.
That is, in most λ-bindings %3dest%1 simply gets bound to %3dest%1.
Since the λ-binding process is not inexpensive
it is tempting to make variables like %3dest%1, which change infrequently,
into non-local variables; they would be initialized at the outside layer
and modified
by side-effects during the evaluation. However the current value
of %3dest%1 %2does%1 need to be saved occasionally. Those occasions
correspond to the places in %3deval%1 ⊗↓%1and its sub-functions← where
%3dest%1 gets rebound to something other than %3dest%1.
We will supply two new primitives to handle explicit saving and restoring
of values:
.BEGIN INDENT 0,6;GROUP;
%21.%1 %3save%1: This binary function would be implemented as a special form.
Its first argument is a name %3old%1, and its second argument is a value %3new%1.
The current value associated with %3old%1 is saved, and the value %3new%1 becomes
the value of %3old%1.
.END
.BEGIN INDENT 0,8;GROUP;
%22.%1 %3restore%1: This is a unary function; its argument is a name %3name%1. The
latest value which was saved for %3name%1 is restored. The value which %3name%1
had on entry to %3restore%1 is lost.
.END
Using %3save%1 and %3restore%1 we could express the evaluation of a
λ-application something like:
.BEGIN;SELECT 3;TABIT2(10,37);GROUP;
\eval[%eR%f(%3 λ[[x;y]%9x%3][a;b] %f)%3; env] =\save[x;a];
\\save[y;b];
\\eval[%eR%f( %9x %f)%3 ;env%9'%3];
\\restore[y];
\\restore[x];
.END
.P200:
The implementation details of %3save%1 and %3restore%1 will not be
needed for most of our discussion, however we include some of them here for
completeness. The information which is %3save%1d and %3restore%1d is
accessible through a global variable named %3control%1. A %3save[%1<name>;<value>]
has the effect of %3concat%1-ing the current value of <name> onto the front of
%3control%1; it then sets the new value of <name> to <value>.
.BEGIN TURN ON "∞" FOR "←"; TURN OFF "←"; NOFILL;
That is: ∞%3control ← concat[eval[%1<name>%3;env];control];set[%1<name>; %3eval[%1<value>%3;env]%1
.END
.BEGIN GROUP;
A %3restore%1[<name>] performs:
.BEGIN CENTER;SELECT 3;TURN OFF "←";
set%1[<name>%3;first[control]]; control ← rest[control]
.END
.END
.BEGIN TURN OFF "←";
The manipulation of %3control%1 by %3save%1 and %3restore%1 is stack-like
in LISP. That means that only the %3first%1 element of %3control%1 is accessible;
to access elements in the interior of %3control%1 requires %3restore%1-ing
down to them by sequence of "%3control%1#←#%3rest[control]%1". Once
we have removed elements from %3control%1 there is no way to access
that information again.
The %3control%1-structure
is not accessible as a data structure to the same degree of generality
as is the access structure. The closest analogy to %3function-funarg%1 is
the %3catch-throw%1 pair. However now that %3control%1 %2is%1 explicit
we can begin to describe extensions to LISP which %2will%1 allow us to capture %3control%1
like %3function%1 captures %3env%1.
.END
Given %3save%1 and %3restore%1 we can rewrite %3deval%1 and its subfunctions
to access non-local representations of variables used in the current %3deval%1.
Thus the evaluator becomes a function of no arguments; it %2knows%1 where to
find the values and it knows how to save and restore those variables.
The result is an evaluator which has even %2fewer%1 implict operations
than %3deval%1.
.BEGIN SELECT 3;TABIT2(15,19);GROUP;
.P196:
deval%9'%3 <= λ[[]\[isconst[] → send[denote[]];
\ isvar[] → send[lookup[]];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\deval%41%3[];
\\restore[args];
\\restore[fun] ]]
.END
Before continuing, a few points should be made. We will be using the same names
as we did in %3deval%1 for all subfunctions of %3deval%9'%1. The difference
will be that here those functions will %2know%1 where their arguments are to be
found; they need not be explicitly passed in. Thus %3send[denote[]]%1
means that %3denote%1 extracts a value from the representation in %3exp%1
and %3send%1 knows that it is to send its value to %3dest%1.
With this new evaluator we can define %3eval%1 as:
.BEGIN TABIT2(15,28);SELECT 3;TURN OFF "←";
\eval <= λ[[x;y]\fun ← ();
\\args ← ();
\\exp ← x;
\\env ← y;
\\dest ← alloc_dest[(TLB)];
\\deval%9'%3[];
\\val[dest]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,26,35;
%1Here is the remainder of %3deval%9'%1:
%3
deval%41%3 <= λ[[]\[isatom[] → \[iscond[] → devcond[];
\\ isprim[] → \save[env;env];
\\\save[dest;alloc_dest[createvars[]]];
\\\evalargs[];
\\\link[];
\\\restore[dest];
\\\execute[];
\\\restore[env];
\\ %et%3 → deval%42%3[] ]
\islambda[] → \save[env;env];
\\save[dest;alloc_dest[vars[]]
\\evalargs[];
\\link[];
\\restore[dest];
\\save[args;bodylist[]];
\\evalargs[];
\\restore[args];
\\restore[env];
\ %et%3 → deval%42%3[] ]]
.END
.BEGIN SELECT 3;TABIT1(14);group;
deval%42%3 <= λ[[ ]\save[exp;fun];
\deval%9'%3[];
\restore[exp];
\save[fun;receive[]];
\deval%41%3[];
\restore[fun] ]
.FILL;SELECT 1;
We introduced %3deval%42%1 to capture the computation to be performed
when the function-position is not recognized as either a λ-expression, a conditional,
or a primitive.
Note that we perform %3save[env;env]%1 in a couple of places in %3deval%41%1.
This is necessary to save the current value of %3env%1 since %3link%1
modifies %3env%1. Indeed, the sequence: save %3env%1 and %3dest%1, %3evalargs%1,
%3link%1, and restore %3dest%1 can be simplified to:
save %3dest%1, %3evalargs%1, followed by %3link%9'%1.
where:
.BEGIN CENTER;SELECT 3;
link%9'%3 <=λ[[] set_int[dest;env];rotate[env;first[control];dest]]
.END
and %3set_int%1 sets the internal pointer of the dest-block to
the current environment, and %3rotate[x;y;z]%1 moves the contents of %3x%1 to %3y%1,
contents of %3y%1 to %3z%1, and contents of %3z%1 to %3x%1.
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,26;
evalargs <= λ[[]\[emptyargs[] → ( );
\ singlearg[] → \save[exp;first[args]];
\\\deval%9'%3[];
\\\restore[exp];
\ %et%3 →\save[exp;first[args]];
\\deval%9'%3[];
\\restore[exp];
\\next[];
\\save[args;rest[args]];
\\evalargs[];
\\restore[args] ]]
.END
Note that we are never interested in the value returned from a
call on a sub-function in the evaluator; all values are passed
explicity from their creator to a destination. We might say that
%3deval%9'%1 never returns a value. In the next section we will
build an evaluator which never returns at all.
.CENT(Problems)
I. Write the new version of %3devcond%1.
II. Examine the %3save-restore%1 sequences in %3deval%9'%1 and its
sub-functions for possible inefficiencies. That is, are all the
saves and restores necessary or could explicit assignments to some of
the non-local variables speed things up?
III. Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.ss(%3eval%1 with explicit control)
Recursion and call-by-value are used to guide the flow of control
in a LISP evaluator. We have started to explore the implementation
of call-by-value, and now we wish to discuss the implementation of
recursion. The mechanisms used in the implementation of any concept
must be of a higher level of detail than the mechanism being implemented.
We cannot use recursion to implement recursion. The basic
purpose of recursive control in the evaluator is to describe
what computation to perform next and to describe where to go when finished.
The evaluator of this section
will rely on explicit directions to tell it what to do next.
The idea is closely related to the logical notion of
%2⊗→continuation↔←s%1 (⊗↑[Wad#74]↑ and ⊗↑[Fis#72]↑)
and thus we will use that terminology here.
In the evaluators of this section we will use the destination to tell where the
result of the current computation is to be put, and use the continuation
to tell what the next computation will be.
Note that the computations in %3deval%1 are basically of two categories:
.BEGIN INDENT 5,5;GROUP;
%21.%1 Simple transformations like sending, building %3dest%1 blocks, or
selecting components of expressions. These computations are non-recursive, requiring
a bounded amount of computation.
.APART
.GROUP
%22.%1 Recursive calls on the evaluator or its subfunctions. These computations
can be arbitrarily complex.
.END
It is the recursive computations which we wish to examine. One of the
implications
of a function call is that we have further computation to be performed
%2after%1 the call is completed. It is the responsibility of the evaluator
to remember where a computation has been interrupted so that
it may pick up where it left off, after completing the call.
One of the major problems in implementing evaluators is "how to remember".
If the function being called is a simple calculation of type %21.%1 above,
then we could replace the call with a copy of the body of the definition
where we have replaced each occurrence of a formal parameter with the
appropriate actual parameter; this works nicely.
Indeed making such formal substitutions
works for computations of type %22.%1 as well.
However the solution in this case is not sufficiently efficient.
In previous evaluators much of the "remembering" was done by recursion in %3eval%1
({yonss(P6)}) and by explicit sequencing in %3deval%1.
We now propose to explicitly %2pass along%1 information about what to
do after the current computation is completed. This information
is called
the %2continuation%1.
The first evaluator of this section is %3ceval%1⊗↓%3c%1 for
%2c%1ontrol or %2c%1ontinuation←;
it is a modification
of %3deval%9'%1 of {yon(P196)}.
It takes a single argument %3c%1 which is a continutation.
The continutation is passed along as a data structure until %3ceval%1
has completed its current computation. At that time %3c%1 is executed.
For example we transform %3deval%9'%1 into %3ceval%1 by forming a continuation
from that portion of %3deval%9'%1 which follows the call on %3deval%41%1. Thus:
.BEGIN SELECT 3;TABIT2(9,13);GROUP;
ceval <= λ[[c]
\[isconst[] → send[denote[]];c[];
\ isvar[] → send[lookup[]];c[];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\ceval%41%3[function[ev1]] ]]
ev1 <= λ[[ ] restore[args]; restore[func]; c[] ]]
.END
For the simple cases we just execute the continuation after the %3send%1;
when we have a function application we make up a new continuation.
When %3ceval%41%1 is finished with the function application
it executes %3ev1%1; that does the %3restore%1 operations and then performs
the saved continuation.
Note the use of %3function%1. The non-local variable %3c%1 in %3ev1%1
represents the continuation passed into %3ceval%1. Therefore %3c%1
must be found in the environment of the body of %3ceval%1 %2not%1
in the environment which is current when %3ev1%1 is applied.
As before, %3eval%1 is expressible with the evaluator:
.BEGIN TABIT2(15,29);SELECT 3;TURN OFF "←";
\eval <= λ[[x;y]\fun ← ();
\\args ← ();
\\exp ← x;
\\env ← y;
\\dest ← alloc_dest[(TLB)];
\\ceval[function[λ[[ ]val[dest]]]] ]
.END
Transforming the sub-functions of %3deval%9'%1 is reasonably straightforward:
the segment of program below a call on one of the recursive parts of the
evaluator is named; a new continuation is made like we did for %3ev1%1;
the transformation process is applied to each new continuation.
For example, here's %3ceval%41%1:
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,26,35;
ceval%41%3 <= λ[[c]\[isatom[] → \[iscond[] → devcond[c];
\\ isprim[] → \save[env;env];
\\\save[dest;alloc_dest[createvars[]]];
\\\evalargs[function[ev2]];
\\ %et%3 → ceval%42%3[];
\islambda[] → \save[env;env]
\\save[dest;alloc_dest[vars[]]
\\evalargs[function[ev5]];
\ %et%3 → ceval%42%3[]] ]]
.END
.BEGIN NOFILL;
%3ceval%42%3 <= λ[[ ] save[exp;fun]; ceval[function[ev3]]]%1
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 9,26,35;
ev2 <= λ[[ ] link[]; restore[dest]; execute[]; restore[env]; c[]]
.APART
.GROUP
ev3 <= λ[[ ] restore[exp]; save[fun;receive[]]; ceval%41%3[function[ev4]]]
ev4 <= λ[[ ]restore[fun]; c[]]
.APART
.GROUP
ev5 <= λ[[ ] link[]; restore[dest]; save[args;bodylist[]]; evalargs[function[ev6]]]
ev6 <= λ[[ ] restore[args]; restore[env]; c[]]
.END
.BEGIN CENTER;GROUP
.CENT(Problems)
I. Write the new version of %3devcond%1 and %3evalargs%1.
II. Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.END
The final step is analogous to that which we performed moving
from %3deval%1 to %3deval%9'%1: we remove the argument to %3ceval%1 and
pass the continuation explicitly in a non-local variable named %3cont%1.
This new evaluator is named %3ceval%9'%1:
.BEGIN SELECT 3;TABIT2(15,19);GROUP;
ceval%9'%3 <= λ[[ ]\[isconst[] → send[denote[]]; cont[];
\ isvar[] → send[lookup[]]; cont[];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\save[cont;function[ev1]];
\\ceval%41%3[] ]]
ev1 <= λ[[ ] restore[args]; restore[func]; restore[cont]; cont[] ]]
.END
We can remove more control structure from the evaluator by noting
that executing the continuation, "%3cont[]%1", and executing the explicit calls
on the evaluator's subfunctions are two manifestations of the same phenomenon.
In the first case we restore to a variable and then execute the variable as a function
application;
in the second, we execute a known call. We can replace these two
actions by a common action if we always execute from the variable %3cont%1 and replace calls
like "%3ceval%41%3[]%1" with the sequence:
.BEGIN CENTER;select 3; turn off "←";
save[cont;function[ceval%41%3]]; cont[];
.end
Notice that when we make this last %3save%1 we know that the current value
of %3cont%1 is %3ev1%1. Notice also that when we execute %3cont[]%1 we
enter %3ceval%41%1 and therefore within this call on %3ceval%41%1,
%3cont%1 %2is%1 %3ceval%41%1. All this discussion can be simplified if we
think a bit about the purpose of continuations: we will need to make note
of what the continuation should be %2after%1 the current computation is
finished; and we will need to set %3cont%1 to designate what computation
to do now. We therefore introduce a binary primitive %3save_cont%1 which
will save its first argument such that %3restore%1 can restore it
to %3cont%1 at the
appropriate time; %3save_cont%1 will set %3cont%1 from its second argument.
.BEGIN SELECT 3;CENTER;TURN OFF "←";
save_cont <= λ[[x;y] cont ← x; save[cont;y]]
.END
We can remove the calls %3cont[]%1, and perform the execution outside
%3ceval%9'%1 using a simple loop:
.BEGIN TABIT3(30,38,40);GROUP;SELECT 3;
.P208:
\loop <= λ[[]prog[[]
\\l\cont[]
\\\go[l] ]]
.END
Each function executed by %3cont[]%1 will perform some simple operations
like %3send%1 or %3alloc_dest%1, and then will exit, setting %3cont%1
to a function name. The next pass around, %3loop%1 will execute
the new %3cont%1. After slight reorganization to eliminate some
%3save-restore%1 operations on %3cont%1, we have:
.BEGIN SELECT 3;TABIT2(15,19);GROUP;turn off "←";
ceval%9''%3 <= λ[[ ]\[isconst[] → send[denote[]]; restore[cont];
\ isvar[] → send[lookup[]]; restore[cont];
\ %et%3 →\save[fun;func[]];
\\save[args;arglist[]];
\\save_cont[quote[ev1];quote[ceval%41%3]] ]]
ev1 <= λ[[ ] restore[args]; restore[func]; restore[cont] ]]
.END
.P204:
Notice the use of %3quote%1 rather than %3function%1.
In the previous evaluators we used %3function%1
since we had to save the current environment; but the continuation
%3c%1 was the
only free variable which was in jeopardy. In %3ceval%9''%1 we have explicitly
saved the continuation using %3save_cont%1, and thus %3quote%1 plus the
proper use of %3restore%1 can replace %3function%1. We will also
introduce an abbreviation, writing %9`%3xx%1 for %3quote[xx]%1⊗↓This
abbreviation is used in several implementations of LISP. See {yon(P157)}.←.
.BEGIN TABIT3(15,32,39);SELECT 3;TURN OFF "←";group;
%1Finally, here's %3eval%1:
%3
\eval <= λ[[x;y]catch[\prog[[ ][\fun ← ();
\\\args ← ();
\\\exp ← x;
\\\env ← y;
\\\dest ← alloc_dest[(TLB)];
\\\save_cont[%9`%3λ[[]throw[val[dest]; out]]]; %9`%3ceval%9''%3];
\\\loop[]];
\\out]]
.END
What has been gained by these transformations of the original %3eval%1?
We have made the mechanisms which were implicit in LISP very explicit.
We have described the implementations of LISP's access and control
requirements in terms of very simple computations. Indeed, we now have
developed enough detail that we can give a faithful implementation description of
all of LISP including the %3function%1 and
%3prog%1 constructs.
.CENT(Problems)
.BEGIN CENTER;
I. Could we use statements like %3save_cont[ev1;eval%41%3]%1 rather than %3save_cont[%9`%3ev1;#%9`%3eval%41%3]%1?
II. Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.END
.SS(An evaluator for %3prog%1,,P211:)
The evaluator in this section will be the definitive interpreter for LISP
throughout the rest of this book. It will handle the applicative subset
of LISP as well as handling %3prog%1s and %3function%1.
.P198:
We need to add more mechanism to handle %3prog%1.
For example the execution of the %3return%1 statement requires that we
locate the dynamically surrounding %3prog%1. The %3go%1 must also locate
its surrounding %3prog%1 which contains the desired label.
The evaluator needs to know when we are evaluating a conditional expression
and when we are evaluating a conditional statement; if we are (immediately) in
a %3prog%1 then its a conditional statement, otherwise its a conditional
expression.
All of this information could be discovered by the evaluator using the currently
supplied information, however the evaluator can be made more efficient
by adding a bit more explicit information. Most of the additions involve
%3prog%1-entry, %3go%1, and %3return%1 and will therefore be presented
when we discuss that part of the evaluator. The only addition we will make now
will be introduction of a variable %3type%1 which is set to %3PROC%1
when we begin an evaluation of an application, and is set to %3PROG%1
when we enter a %3prog%1.
We will also rework some of our current sub-functions to aid
clarity and efficiency.
Since sequences of %3save%1s happen frequently in the evaluators
we introduce a new procedure named %3save%9'%1 which acts like
a sequence of calls on %3save%1 for arguments other than %3cont%1.
In this latter case, a call on %3save_cont%1 is simulated.
Similarly we introduce an iterated version of %3restore%1 named %3restore%9'%1.
.BEGIN SELECT 3;TABIT3(14,19,24);GROUP;turn off "←";
peval <= λ[[ ]\[isconst[] → send[denote[]];restore[cont];
\ isvar[] → send[lookup[]];restore[cont];
\ %et%3 →\save%9'%3[\fun;func[];
\\\args;arglist[];
\\\cont;#%9`%3ev1;#%9`%3peval%41%3] ]]
ev1 <= λ[[ ] restore%9'%3[args;func;cont] ]]
.END
.P201:
The responsibility of %3peval%1 is simply to recognize the occurrence
of one of the basic forms: a variable, a constant, or a function application.
Discovering the structure of an application is the business of %3peval%41%1.
We need to know whether the function position represents a call-by-value
function or a special form. So far the only special form we recognize is
%3cond%1⊗↓Actually %3quote%1 is also a special form which we recognize,
however its recognition is handled within %3isconst%1.←;
however many of the constructs which %3prog%1 introduced
are special forms. We could add a collection of recognizers %3issetq%1, %3isgo%1,
%3isprog%1, etc., to augment the existing %3iscond%1. Instead we would
rather add a device similar to %3isprim%1 but instead of handling the call-by-value
primitives with the underlying evaluator, we wish to handle special forms with
our own pieces of %3peval%1. We need a predicate named %3isspec%1
to recognize occurrences of special forms and
will need to add functions to %3peval%1 to execute the appropriate
programs when %3isspec%1 is true. We will do this by introducing a
global table called %3spectbl%1. The name components of the
table will be the names for special forms; the value components of %3spectbl%1
will be the names of functions which will evaluate the corresponding special
form⊗↓In the next chapter we will see a more efficient way to recognize and
execute special forms.←.
Then we can write:
.BEGIN SELECT 3;GROUP;TABIT2(15,26);
\isspec <= λ[[ ][null[nassoc[fun;spectbl]] → %ef%3; %et%3 → %et%3]
\nassoc <= λ[[x;l][null[l] → ( ); %et%3 → assoc[x;l]]
.END
To execute the appropriate routine we need only put the name in the variable
%3cont%1 and %3loop%1 will do the rest. We can load %3cont%1 by:
.BEGIN CENTER;SELECT 3; TURN OFF "←";
cont ← valspec[ ]; %1where:### %3valspec <= λ[[ ]value[nassoc[fun;spectbl]]]
.END
For example, with %3spectbl%1 bound to %3((COND DEVCOND))%1,
our previous %3ceval%41%1 would work quite nicely as:
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 14,23,35;turn off "←";
ceval%41%3 <= λ[[ ]\[isatom[] → \[isspec[] → cont ← valspec[ ];
\\ isprim[] → \save[env;env];
\\ ... ] ... ]]
.END
Before introducing %3peval%41%1 we should say a bit about the inefficiency
involved in the %3isspec%1-%3valspec%1 pair. We already noted that
the linear search encoded in %3assoc%1 is unnecessarily inefficient.
However the present predicate-function pair is even more wasteful;
if %3isspec%1 %2is%1 true we perform %3nassoc[fun;spectbl]%1 twice.
A more efficient computation would save the result of the first
call on %3nassoc%1 in a temporary variable %3t1%1 and if %3isspec%1
is true, move the %3value%1-part of %3t1%1 to %3cont%1. Thus:
.BEGIN SELECT 3;GROUP;TABIT2(15,28);TURN OFF "←";
.P219:
\isspec <= λ[[ ]\t1 ← assoc[fun;spectbl]]
\\[null[t1] → %ef%3; %et%3 → %et%3] ]
%1with:\%3valspec <= λ[[ ]value[t1]]
.END
This is a useful programming trick but does not add to the clarity of the
program. In {yonss(P214)} we shall see a more subtle, but related trick.
.BEGIN GROUP;TURN ON "\";NOFILL; TABS 15,26,31,35,40;turn off "←";
.BEGIN SELECT 1;FILL;
What follows is the remainder of the evaluator interspersed with commentary.
The main function is %3peval%41%1; it handles function applications.
The application is
either a call-by-value application or it is a special form. An instance
of the first requires evaluation of the argument list and then evaluation
of the procedure body. If the application is a special form then
the evaluation is handled by a special piece of the evaluator, using
the mechanism described above. The call-by-value applications are either primitive
applications or are anonymous λ-terms. If the form is not recognizable then
the function-position is evaluated and then applied to its argument list.
The anomalous situation involves the application of a %3funarg%1; though
it is possible to handle this case as a primitive, it is more instructive
to present it in detail. Here is %3peval%41%1:
.END
.P203:
%3peval%41%3 <= λ[[ ]\[isatom[] → \[isspec[] → cont ← valspec[ ];
\\ isprim[] → \save%9'%3[\env;env;
\\\\\dest;alloc_dest[createvars[]];
\\\\\cont; %9`%3ev2; %9`%3evalargs];
\\ %et%3 → save%9'%3[exp;fun;cont; %9`%3ev3; %9`%3peval];
\islambda[] → \save%9'%3[\env;env;
\\\dest;alloc_dest[vars[];
\\\cont; %9`%3ev5; %9`%3evalargs];
\isfunarg[] →\prog[[x;y]\x ← args;
\\\\args ← bodylist[second[fun]];
\\\\y ← env;
\\\\env ← third[fun];
\\\\save%9'%3[\env;env;
\\\\\args;x;
\\\\\dest;alloc_dest[vars[second[fun]]];
\\\\\env;y;
\\\\\cont; %9`%3ev7; %9`%3evalargs]];
\ %et%3 → save%9'%3[exp;fun; cont; %9`%3ev3; %9`%3peval] ]]
.END
.BEGIN GROUP;TURN ON "\";NOFILL; TABS 9,26,35;turn off "←";
The functions %3ev2%1 through %3ev8%1 handle the control in %3peval%41%1:
.SELECT 3;
.P232:
.BEGIN CENTER;
ev2 <= λ[[ ] link[]; restore[dest]; execute[]; restore%9'%3[env;cont]]
.END
%1This function passes the evaluation to the body of the primitive.%1
.APART
.GROUP
.BEGIN CENTER;
%3ev3 <= λ[[ ] restore[exp]; save%9'%3[fun;receive[];cont; %9`%3ev4; %9`%3peval%41%3]]
.END
.BEGIN SELECT 1;FILL;
%3ev3%1 is the return point when we have to evaluate the function position of a form.
When %3ev3%1 is called the result of that evaluation is in the current dest-slot.
A %3receive%1 gets the value; we then pass the new form back to %3peval%41%1.
.END
.BEGIN CENTER;select 3;
ev4 <= λ[[ ] restore%9'%3[fun;cont]]
.END
.BEGIN CENTER;select 3;
ev5 <= λ[[ ] link[]; restore[dest]; save%9'%3[args;bodylist[]; cont; %9`%3ev6; %9`%3evalargs]]
.END
.BEGIN FILL;SELECT 1;
%3ev5%1 handles the evaluation of the body of a λ-expression. Since we are
allowing multiple-bodied λ-expressions ({yon(P193)}), we pass the %3bodylist%1
to %3evalargs%1. If we were restricting ourselves to single-bodied expressions,
then passing %3body%1 to %3peval%1 would suffice.
.END
.BEGIN CENTER;select 3;
ev6 <= λ[[ ]restore%9'%3[args;env;cont]]
.END
.APART
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 12,26,35;turn off "←";
.SELECT 1;
The functions %3ev7%1 and %3ev8%1 control the application of a %3funarg%1.
.SELECT 3;
ev7 <= λ[[ ]\restore[env];
\link[];
\restore%9'%3[dest;args];
\save_cont[ %9`%3ev8; %9`%3evalargs] ]]
ev8 <= λ[[ ] restore%9'%3[env;cont]]
.END
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,35;TURN OFF "←";
.BEGIN FILL;SELECT 1;
The next four functions handle the evaluation of a sequence of expressions.
If the sequence is empty, then there is noting to do. If there is a single
argument then evaluate it and restore the continuation.
Otherwise evaluate the first one using
%3peval%1 (sending its result to %3dest%1) and then execute %3ev11%1.
At %3ev11%1 we update the destination block using %3next%1 and get set to
evaluate the next argument.
.END
.P231:
evalargs <= λ[[]\[emptyargs[] → restore[cont];
\ %et%3 → \save[exp;first[args]];
\\cont ← %9`%3ev9 ]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 11,16,23;turn off "←";
ev9 <= λ[[ ]\[singlearg[] → \save_cont[ %9`%3ev10; %9`%3peval];
\ %et%3 →\save_cont[ %9`%3ev11; %9`%3peval] ]]
ev10 <= λ[[ ] restore%9'%3[exp;cont]]
e11 <= λ[[ ]\next[];
\args ← rest[args];
\exp ← first[args];
\cont ← %9`%3ev9 ] ]
.END
.BEGIN GROUP;
.CENT(Problem)
.CENTER
Using the new evaluator, sketch the evaluation of %3f[A]%1 where: %3f#<=#λ[[x]eq[x;A]]%1.
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,27;turn off "←";
.P233:
.BEGIN FILL;SELECT 1;
The combination of %3evcond%1 and %3cond1%1 handle conditional expressions⊗↓See
the problem on {yon(P197)}.←.
%3evcond%1 sets up the evaluation of the predicate position such that the
computation will continue at %3cond1%1. When that evaluation is completed %3cond1%1
%3receive%1s the result. If %et%1 is received then the consequent part of that
conditional clause evaluated. Note that we use %3evalargs%1 here since
we allow extended conditionals ({yon(P194)}).
If %ef%1 is received we go back to %3evcond%1 with the remaining part of the
conditional.
.END
evcond <= λ[[ ]\[emptyargs[] →\err[NO_TRUE_COND_CLAUSE];
\\\cont ← %9`%3ev1;
\ %et%3 → \save_cont[ %9`%3cond1; %9`%3peval];
\\exp ← pred[first[args]] ]]
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,26;turn off "←";
cond1 <= λ[[ ]\[receive[] → \args ← conseq[first[args]];
\\\save_cont[ %9`%3ev1; %9`%3evalargs];
\ %et%3 →\args ← rest[args];
\\cont ← %9`%3evcond ]]
.END
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 18,24,35;turn off "←";
.BEGIN FILL;SELECT 1;
The next two functions deal with functional arguments.
If the argument is a primitive, then we just %3quote%1 it; the assumption
is that primitives only access local variables and therefore don't need to save the
environment. An expression which is already %3funarg%1-ed is passed as is.
If it is a λ-expression, we make a %3funarg%1; otherwise we evaluate the
function until we discover its character.
.END
evfunction <= λ[[ ]\fun ← first[args];
\[isprim[] → send[mkquote[fun]];restore[cont];
\ islambda[] → send[mkfunarg[fun;env]];restore[cont];
\ isfunarg[] → send[fun];restore[cont];
\%et%3 → \save_cont[ %9`%3fun1; %9`%3peval];
\\exp ← fun ]]
fun1 <= λ[[ ] send[mkfun[receive[ ]]; cont ← %9`%3ev1]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 13,18,35;turn off "←";
.BEGIN FILL;SELECT 1;
Special functions are needed to handle explicit calls on the evaluator:
%3eval%1[<form>;<env>]. We set up a destination to receive the values
of <form> and <env>, and ask %3evalargs%1 to evaluate these arguments.
The results of the computation are seen by %3ev12%1; this function sets up
the call on %3peval%1.
.END
eveval <= λ[[ ]\save%9'%3[\env;env;
\\dest;alloc_dest[createvars[(G1 G2)]];
\\cont; %9`%3ev12; %9`%3evalargs]]
ev12 <= λ[[ ]\exp ← first_dest[];
\env ← second_dest[];
\restore[dest];
\save_cont[ %9`%3ev13; %9`%3peval]]
ev13 <= λ[[ ] restore%9'%3[env;cont]] (%c≡%3 ev8)
.END
.P205:
There is a second form of call on %3eval%1 which is useful. If we
write %3eval%1[<form>], then the <form> is evaluated in the environment
which exists at the point of call. See problem on {yon(P206)}.
.BEGIN SELECT 1;FILL
The remainder of the evaluator involves the semantics of %3prog%1s.
Several new ideas are involved. As we discussed on {yon(P198)},
we must be able to determine
whether or not we are executing within a %3prog%1: we introduced
%3type%1 to handle this.
Also every expression or statement in LISP has a value. Since we are always
%3send%1-ing values, we must have a destination to receive the values
created by %3prog%1#statements: we will introduce a dummy destination which
will always receive the value of any statement. This destination is named
%3bb%1, for "bit#bucket".
Finally, we must handle assignment statements. The innovation here
is that the %3send%1 goes to some pre-existing destination and destroys the
current value: we use a primitive %3mkdest%1 whose effect is to
generate a destination pointer to the slot which is to receive the value of
the right-hand-side of the assignment.
In %3evsetq%1
we use a function %3lookup%9'%1 which is similar to %3lookup%1 except
that it returns a pointer to the slot containing a value, rather than
returning the value in the slot.
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 14,19,37;turn off "←";
.SELECT 1;
Here are the evaluators for %3setq%1 and %3set%1:
.SELECT 3;
evsetq <= λ[[ ]\save%9'%3[\dest;mkdest[lookup%9'%3[first[args]]];
\\cont; %9`%3setq1; %9`%3peval];
\exp ← second[args]]
setq1 <= λ[[ ]\prog[[x]
\\x ← receive[];
\\restore[dest];
\\send[x];
\\cont ← %9`%3ev1 ]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 12,26,35;turn off "←";
evset <= λ[[ ]\save%9'%3[args;args; cont; %9`%3set1; %9`%3peval];
\exp ← first[args] ]
set1 <= λ[[ ]\restore[args];
\args ← mkass[receive[];rest[args]];
\cont ← %9`%3evsetq ]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,20,35;turn off "←";
.BEGIN SELECT 1;FILL
The %3prog%1 evaluator, %3evprog%1, must take cognizance of all of the control
structures which can occur within a %3prog%1. Besides ordinary recursion, we
can have %3go%1s and %3return%1s. The %3go%1 must be able to search the
dynamic chain for the appropriate label, and the %3return%1 must find the
dynamically enclosing %3prog%1.
To handle either of these eventualities, we %3save%1 some additional information
when we enter a %3prog%1. First we save the current state of the computation;
this will allow the %3return%1 to %3restore%1 everything as it leaves the %3prog%1.
Next we make a new %3env%1 which has bound all the %3prog%1#variables to %3(#)%1.
We save %2that%1 %3env%1, since a non-local %3go%1 will want to restore that
%3env%1 as it returns for execution. Finally we create a %3golist%1 which is a list
of all points in the %3prog%1 which have labels. This construct allows
us to discover quickly which labels are present in the %3prog%1 and where they
are⊗↓If it weren't for the existence
of anonymous %3prog%1s and function-modifying functions, we could put
the responsibility of making the go-list
on "<=".←. After
all this is done we are ready to execute the first line of the
%3prog%1#body.
.END
evprog <= λ[[ ]\save%9'%3[\exp;exp;
\\env;env;
\\dest;alloc_dest[prog_vars[args]];
\\fun;fun;
\\args;prog_body[args];
\\type;PROG];
\link[];
\save%9'%3[\env;env;
\\golist;mkgolist[args]];
\cont ← %9`%3line ]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 20,23;turn off "←";
mkgolist <= λ[[body] prog[z]
\a\[null[body] → return[z];
\\ islabel[first[body]] → z ← concat[body;z] ];
\\body ← rest[body];
\\go[a] ]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 12,23,32;turn off "←";
.BEGIN SELECT 1;FILL;
The actual execution of each line of a %3prog%1#body is controlled by the
pair %3line%1 and %3line1%1. Their behavior is similar to that
of the functions within %3evalargs%1. %3line%1 examines the next expression;
if there is no next statement, we exit with %3(#)%1 using %3prog_exit%1;
if the next statement is a label, it is ignored; otherwise we set up to
evaluate the expression, setting the destination to %3bb%1.
.END
line <= λ[[ ]\[null[args] → prog_exit[( )];
\ islabel[first[args]] → args ← rest[args];
\ %et%3 → \exp ← first[args];
\\dest ← bb;
\\save_cont[ %9`%3line1; %9`%3peval] ]]
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 12;turn off "←";
line1 <= λ[[ ]\args ← rest[args];
\cont ← %9`%3line ]
.SELECT 1;FILL;
Note that we don't change %3cont%1 in %3line%1 when we see a label; we just
leave it at %3line%1 and %3loop%1 does the rest.
.END
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 15,26,35;turn off "←";
.BEGIN FILL SELECT 1;
We call %3prog_exit%1 to return %3(#)%1 when the body of the %3prog%1 is empty.
Thus
the discussion of %3prog_exit%1 involves the semantics of %3return%1.
Of the two control mechanisms, %3return%1 is simpler than %3go%1.
Recalling the discussion of %3save%1 on {yon(P200)},
we need to look through the %3control%1-list for the last block
designating a %3prog%1 entry. We %3restore%1 to that saved
state and set %3control%1 to that prior point.
.END
evreturn <= λ[[ ]\exp ← first[args];
\save_cont[ %9`%3ret1; %9`%3peval] ]
ret1 <= λ[[ ] prog_exit[receive[]]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 19;turn off "←";
prog_exit <= λ[[val]\control ← find_prog[control];
\restore%9'%3[type;args;fun;dest;env;exp;cont];
\send[val] ]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 12,24;turn off "←";
.BEGIN SELECT 1;FILL;
The %3go%1 statement is a bit more complicated.
When a %3go%1 statement is recognized, we look back through the dynamic
chain to find the first occurrence of the desired label. If we are in a %3prog%1
we check the current %3golist%1; if the label is not found, or if we are not
immediately in a %3prog%1, we look for the latest %3golist%1 and
search it. We continue this process until we discover the label. At that time we
restore the environment to that which was current,
reset %3control%1, and continue the computation
at that point.
.END
evgo <= λ[[ ]\exp ← first[args];
\[isconst[] →err[BAD_PROG_LABEL];
\ not[isvar[]] → \save_cont[ %9`%3go1; %9`%3peval]
\ %et%3 → control ← prog_go[control;exp] ]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 22,24,39,63;turn off "←";
prog_go <= λ[[cntrl;exp]prog[[ ]
\a\[eq[type;PROG] →\[check_go[exp;golist[cntrl]] →\restore[env];
\\\\cont ← %9`%3line;
\\\\return[cntrl]
\\\ %et%3 → cntrl ← find_go[rest[cntrl]]; go[a] ];
\\ %et%3 → cntrl ← find_go[cntrl]; go[a] ]]]
.END
.BEGIN SELECT 3;GROUP;TURN ON "\";NOFILL; TABS 22,35;turn off "←";
check_go <= λ[[lab;glist]\[null[glist] → %ef%3;
\ eq[lab;first[first[glist]]] → args ← rest[first[glist]];%et%3;
\ %et%3 → check_go[lab;rest[glist]] ]]
.END
The origins of the interpreter presented here can be traced from several
sources: ⊗↑[Bla#71]↑, ⊗↑[Con#73]↑, ⊗↑[Sus#76]↑, ⊗↑[Ste#76b]↑.
.CENT(Problems)
I. This problem involves the %3escape%1 expression discussed in ⊗↑[Rey#68]↑
and implemented in the University of Paris's LISP ⊗↑[Gre#75]↑.
We introduce the form:
.BEGIN CENTER;SELECT 3;
escape%1[<function>; <form%41%1>; ...;<form%4n%1>]
.END
with the following semantics: we evaluate the <form%4i%1>'s from left to right,
returning the value of <form%4n%1> unless we encounter an application involving
<function>. If such an application %2does%1 appear we perform that application
and immediately return the resulting value as the value of the %3escape%1 expression.
Extend our latest evaluator to recognize and execute the %3escape%1
expression.
II. The semantics of %3go%1 specified that the argument would be evaluated
if it were a function application, however the current %3peval%1
does not handle this case. Correct that oversight.
.P197:
III. Extend %3evcond%1 to handle conditional statements.
IV. Recall our discussion on {yon(P200)} of the implementation of
%3save%1 and %3restore%1. Implement %3save%1 and %3restore%1 in %3peval%1.
V. Write %3find_go%1 and %3find_prog%1.
.P206:
VI. Revise %3eveval%1 to handle calls on %3eval%1 with either one or two
arguments. See {yon(P205)}.
VII. MULTIPLE SETQS
.SS(Alternatives to %3eval%1)
We have seen a lot of evaluators for LISP. We should at least look
a bit at other possibilities for describing computational behavior.
Indeed, what is "computation"? When we are given an expression to evaluate
we are really simulating the application of simplification and substitution rules.
The simplification rules tell us when an expression can be replaced
by another expression; typically we think of the replacing expression
as being "simpler" than the replaced expression. Thus %3car[(A#.#B)]%1
can be replaced by %3A%1, or %3[%et%1#→#2;#...]%1 can be replaced by %32%1.
The substitution rules typically allow us to replace a procedure call
with an appropriately instantiated copy of the procedure body.
Thus a computation involving %3append[(A#B);(2#3)]%1 is identical to
that obtained by replacing the occurrence of
.BEGIN CENTER;SELECT 3;
append[(A B);(2 3)]%1 by%3 [null[(A B)] → (2 3); %et%3 → concat[first[(A B)];append[rest[(A B)];(2 3)]]]
.END
The result of such a substitution is usually a candidate for further substitutions
and simplifications.
The collection of simplification and substitution rules is called the reduction rules
for the language. Given an expression, a computation
of its value is said to terminate when
there are no further reduction rules applicable and the reduced expression
is a constant of the language.
The difficulties with these schemes come from both practical and theoretical
considerations. The direct application of reduction rules is quite inefficient:
making textual substitutions is expensive. Instead we developed the ideas of symbol tables
to contain the bindings of the variables, rather than perform the actual
substitutions.
The theoretical difficulty appears since, at any time in a computation, there
may be more than one reduction rule which is applicable. A further difficulty
is that one sequence of reductions may terminate, while another sequence of reductions
is non-terminating. We have seen this phenomenon in previous discussions of
call-by-value versus ⊗→call-by-name↔←, and inner-most versus outer-most.
LISP opted for the call-by-value interpretation of expressions. It is possible
to develop a call-by-name evaluator. Call-by-name implies that we substitute
the unevaluated actual parameters for the formal parameters.
As in %3eval%1, we need not make explicit substitutions;
appropriate use of symbol tables will simulate the action.
But now, when we build a symbol table on entry to a λ-expression
we bind the actual expressions to the λ-variables;
when we encounter a variable in the body of the expression
we evaluate the actual parameter. The difficulty is that an actual parameter
itself
may contain variables, and those variables need to be interpreted
in the binding environment. This means that we must bind
%3funarg%1-like expressions to the formal parameters.
Most of %3eval%4name%1 is like %3eval%1 of {yonss(P6)}, so we only
sketch the interesting parts. Assume the %3funarg%1-expression we manufacture
has two components, the %3expr%1-component, and the %3env%1-component.
We can implement %3eval%4name%1 by simply changing the symbol table orgainzation,
supplying new versions of %3lookup%1 and %3mkenv%1. See {yon(P212)} and {yon(P218)}.
.BEGIN CENTERIT;GROUP;select 3;tabit1(16);
←alloc <= λ[[vars] ()]
←send <= λ[[var;val;dest] concat[mkent[var;val];dest]
←link <= λ[[dest;env] concat[dest;env]]
lookup <= λ[[var;env] l%9'%3[var;first[env];rest[env]]
l%9'%3 <= λ[[n;bl;env]\[null[bl] → l%9'%3[n;first[env];rest[env]]
\ eq[n;name[first[bl]] → eval[value[first[bl]];env]
\ %et%3 → l%9'%3[n;rest[bl];env] ]]
.END
One advantage of such an evaluator is that it will not evaluate
a parameter until it actually needs it, whereas %3eval%1 evaluates
all parameters at function entry time. If an actual parameter is not
used in the computation and the computation of that parameter
fails to terminate, then %3eval%4name%1 will terminate
while %3eval%1 will not.
There are disadvantages to %3eval%4name%1. Every occurrence of a variable
within the body of the function will involve a re-evaluation of the
corresponding actual parameter. If there are no side-effects in the computation
then these further computations are an unnecessary expense. Several people
(⊗↑[Wad#71]↑, ⊗↑[Vui#73]↑, ⊗↑[Pac#73]↑, ⊗↑[Hen#76]↑, ⊗↑[Fri#75a]↑) have suggested
modifications to %3eval%4name%1 to reduce the inefficiency.
The basic idea, named ⊗→call-by-need↔← is to proceed in the %3eval%4name%1 style until the first
use of a variable. At that time we evaluate the actual parameter, and
modify the symbol table,
%2replacing%1 the actual parameter with its value. Further references to that
variable simply get the value. Obviously the scheme
will not work correctly if side-effects are present.
We leave it to the reader to supply the details of %3eval%4need%1. See
{yon(P199)}.
We now explore a different kind of modification to LISP. This one is
grounded more in practical experience with the programming language,
though the results do have theoretical interest. It has been noted
that programmers frequently wish to return more than one value as the result of
a function application. The standard alternatives are to make global assignments
from within the body of the function, or to return a list of the desired values
making it the responsibility of the calling program to select the proper
components. Neither alternative is particularly good. Programming with
side-effects tends to lead to obscure programs; passing lists back as values
requires much additional computation: someone must build the list; someone
must tear it apart. It is also disturbing that the operation being modelled,
--multiple-values--, is not recognizable as a construct. This is a similar
complaint to that we raised in discussing labels-and-%3go%1s versus an
iterative construct.
Our goal is realizable by a slight extension of the extended conditionals
and multiple-bodied
λ-expressions ({yon(P194)},#{yon(P193)}).
We will interpret the form:
.BEGIN CENTER
p%4i%*#→#e%4i1%*; ... e%4in%*.
.END
as returning the e%4ij%1-values to the calling function in a left-to-right
order. If the calling program is single-valued then the value it sees is
the value of e%4in%1. This is compatible with our current interpretation.
The evaluation of:
.BEGIN CENTER;
%3λ[[#...#]f%41%*[#...#];#...;#f%4n%*[#...#]]%1
.END
will be interpreted similarly.
For example ⊗↑[Fri#75]↑ discusses a multiple-valued function named
%3sigmasum%1. This function is to take a list of numbers and return three
items: the length of the list, the sum of the numbers in the list, and
the sum of the squares of the numbers in the list.
In our notation %3sigmasum%1 can be expressed as:
.BEGIN SELECT 3; GROUP;TABIT3(18,24,32);
sigmasum <= λ[[x]\[null[x] → 0;0;0;
\ %et%3 → λ[\[z%41%3;z%42%3;z%43%3]\add1[z%41%3];
\\\plus[first[x];z%42%3];
\\\plus[times[first[x];first[x]];z%43%3] ]
\\[sigmasum[rest[x]]] ]]
.END
Notice that we use an anonymous λ-expression to spread the multiple values at the
level of the caller.
.GROUP;
Another example is a solution to the %3samefringe%1 problem: determine whether or
not the terminal nodes of two trees are the same, respecting order, but
irrespective of tree structure. Thus:
.BEGIN CENTER;SELECT 3;
samefringe[(A (B (C))); (A B C)] = %et%1 but %3samefringe[(A (B C)); (A C B)] = %ef%1.
.END
.BEGIN SELECT 3;TABIT2(20,25);
samefringe <= λ[[x;y]\[null[x] → null[y];
\ %et%3 → \λ[[z%41%3;z%42%3;z%43%3;z%44%3][eq[z%41%3;z%43%3] → samefringe[z%42%3;z%44%3]; %et%3 → %ef%3]]
\\ [fringe[x];fringe[y]] ]
.END
.APART;
.GROUP;
.BEGIN SELECT 3;TABIT3(16,22,30);
fringe <= λ[[x]\[atom[first[x]] → first[x]; rest[x];
\ %et%3 → \λ[[y;z] y;\[null[z] → rest[x];
\\\ %et%3 → cons[z; rest[x]] ] ]
\\ [fringe[first[x]]] ] ]
.END
In this solution, %3samefringe%1 is single-valued but uses values from a multiple-valued
function. The two values from %3fringe[x]%1 are spread into %3z%41%1 and %3z%42%1
and the values from %3fringe[y]%1 are spread into %3z%43%1 and %3z%44%1.
.APART;
.BEGIN GROUP;
It is easy to write an evaluator for such multiple-valued expressions.
Here is a sketch of the basic parts:
.BEGIN SELECT 3;TABIT3(15,27,35);
meval <= λ[[x;e]\[isconst[x] → list[denote[x]];
\ isvar[x] →list[lookup[x;e]];
\ iscond[x] → mevcond[condbody[x];e];
\ %et%3 → mapply[fun[x];mevlist[arglist[x];e];e] ]]
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT3(22,34,42);
mapply <= λ[[fn;args;e]\[isprim[fun] →list[apply[fun;args;e]]
\ islambda[fun] → mevlist[\bodylist[fun];
\\\mkenv[vars[fun];args;e] ]
\ %et%3 → mapply[eval[fun;e];args;e] ]]
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT3(15,27,35);
mevlist <= λ[[l;e]\[null[l] → ();
\ %et%3 → append[meval[first[l];e]; mevlist[rest[l];e]] ]]
.END
.APART
.GROUP
.BEGIN SELECT 3;TABIT3(17,27,35);
mevcond <= λ[[l;e]\[null[l] → ();
\ first[meval[pred[first[l]];e]] → mevlist[conseq[first[l];env];
\ %et%3 → mevcond[rest[l];e] ]]
.END
.END
.CENT(Problems)
I. Complete the specification of %3eval%4name%1.
.P199:
II. Complete the specification of %3eval%4need%1. To do this, you many
assume the existence of a binary function named %3stuff%1 whose first argument
%3x%1 is
the a name in the symbol table, and whose second argument %3y%1 is a value.
%3stuff%1 is to replace the current binding of %3x%1 with %3y%1.
III. Modify %3peval%1 to handle multiple-valued functions.
IV. Recall the problem on {yon(P221)} dealing with the analysis of
%3lookup%1. Include call-by-name and call-by-need in your
analysis.
V. Using the results of the previous problem, make up a table
whose rows are labeled with the binding implementations: "deep"
"shallow", "Weizenbaum", "need", and "name"; and whose
columns are labeled with the prmitives: %3alloc%1, %3link%1, %3send%1,
and the primitives for %3lookup%1. Supply the entries.